Software transactional memory (STM) is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. A transaction in the context of transactional memory is a piece of code that executes a series of reads and writes to shared memory. STM is used as an alternative to traditional locking mechanisms. STM allows concurrent programs to be written more simply. A transaction specifies a sequence of code that is supposed to execute as if it were executing in isolation. This illusion of isolation is achieved by fine-grained locking of objects, and by executing in a mode that allows the side-effects of the transaction to be rolled back if the transaction is discovered to be in conflict with some other transaction. We say that a data access is “transacted” if the code generated for that access has been modified to include support for these locking and rollback mechanisms.
Many STM systems support nested transactions, allowing efficient composition of different components authored using transactions. A nested transaction is considered closed if it its effects are part of the same isolation boundary as its containing, or parent, transaction. When a closed nested transaction commits, its effects do not become visible to the rest of the system. Instead, its effects become part of the parent transaction, still in progress, and will become visible to the rest of the system only when the parent transaction finally commits. When a nested transaction rolls back, its temporary effects are undone and the state of the parent transaction is restored to the point that the nested transaction began.
STM systems that use in-place writes and optimistic reads use a version number associated with each lockable region of memory to indicate when changes are made to shared data. A reading transaction will optimistically record the version number of the memory (object, cache line, etc.) but not otherwise lock the data. The transaction may commit if the version number does not change over the life of the transaction. Writing transactions increment the version number when releasing their write locks, either for commit or rollback. The version number must be increased during rollback because the writing transaction temporarily updated data in-place. These updates are visible to the reading transaction, and it must be notified that it cannot commit, having potentially read inconsistent data.
Nested transactions that write data not yet written by the parent must increment version numbers on rollback just like non-nested (top-level) transactions. However, consider the case where a parent transaction optimistically reads a variable X and a nested child transaction writes to variable X for the first time. The parent will record the version number of X in its log, say, version V1. The nested transaction will begin and acquire a write lock on X. If the nested transaction commits, then there are no problems: the write lock is not released and is transferred to the parent and the parent remains consistent, able to commit. However, if the nested transaction rolls back, for whatever reason, it must release the write lock and increment the version number for X to V2. The parent will appear to be inconsistent at commit time. The version of X is V2, but the parent read it at V1 and has no record of who changed the version number to V2. It appears that the parent has conflicted with another transaction, but in fact it was a nested child transaction that caused the version number increase, and this is not actually a conflict. The parent has been doomed by its child's rollback operation. This problem causes STM systems to experience spurious re-executions of parent transactions.